If $G$ is a $k$-chromatic graph of order $n$ then it is known that thechromatic polynomial of $G$, $\pi(G,x)$, is at most $x(x-1)\cdots(x-(k-1))x^{n-k} = (x)_{\downarrow k}x^{n-k}$ for every $x\in \mathbb{N}$. Weimprove here this bound by showing that \[ \pi(G,x) \leq (x)_{\downarrow k}(x-1)^{\Delta(G)-k+1} x^{n-1-\Delta(G)}\] for every $x\in \mathbb{N},$ where$\Delta(G)$ is the maximum degree of $G$. Secondly, we show that if $G$ is aconnected $k$-chromatic graph of order $n$ where $k\geq 4$ then $\pi(G,x)$ isat most $(x)_{\downarrow k}(x-1)^{n-k}$ for every real $x\geq n-2+\left( {n\choose 2} -{k \choose 2}-n+k \right)^2$ (it had been previously conjecturedthat this inequality holds for all $x \geq k$). Finally, we provide an upperbound on the moduli of the chromatic roots that is an improvment over knownbounds for dense graphs.
展开▼
机译：如果$ G $是阶次$ n $的$ k $色图，则已知$ G $的色多项式$ \ pi（G，x）$最多为$ x（x-1）\ cdots（x-（k-1））x ^ {nk} =（x）_ {\ downarrow k} x ^ {nk} $每\ x \ in \ mathbb {N} $中的$。通过显示\ [\ pi（G，x）\ leq（x）_ {\ downarrow k}（x-1）^ {\ Delta（G）-k + 1} x ^ {n-1 -\ Delta（G）} \] \ mathbb {N}中的每个$ x \ $，其中$ \ Delta（G）$是$ G $的最大程度。其次，我们表明如果$ G $是一个连接的$ k $阶图-n $$-的色图，其中$ k \ geq 4 $则$ \ pi（G，x）$最多为$（x）_ {\ downarrow k }（x-1）^ {nk} $代表每一个实数$ x \ geq n-2 + \ left（{n \ choose 2}-{k \ choose 2} -n + k \ right）^ 2 $（it先前曾推测此不等式适用于所有$ x \ geq k $）。最后，我们提供了色根模量的上限，这是对稠密图已知边界的改进。
展开▼
